package tree;

import sun.reflect.generics.tree.Tree;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;

public class TreeDepth {
    public static void main(String[] args) {
        int[] arr = new int[]{3,9,2,0,0,1,7};
        TreeNode treeNode = initTreeNode(arr);
        List<Integer> leaf = getLeaf(treeNode, new ArrayList<Integer>());
        System.out.println(leaf);
        //层序遍历二叉树
//        LinkedList<TreeNode> ll = new LinkedList<>();
//        ll.add(treeNode);
//        TreeNode currentNode;
//        while(!ll.isEmpty()){
//            currentNode = ll.poll();
//            System.out.println(currentNode.val);
//            if(currentNode.left != null){
//                ll.add(currentNode.left);
//            }
//            if(currentNode.right != null){
//                ll.add(currentNode.right);
//            }
//        }
        //
//        int maxDepth = getMaxDepth(treeNode);
//        System.out.println(maxDepth);
//        List<Integer> integers = rightSideView(treeNode);
//        System.out.println(integers);
    }
    //通过数组构建一棵二叉树
    public static TreeNode initTreeNode(int[] elements){
        if(elements.length <=0){
            return null;
        }
        List<TreeNode> list = new ArrayList<>();
        TreeNode root = new TreeNode();
        //将数组添加到节点列表
        for (int i = 0; i < elements.length; i++) {
            list.add(new TreeNode(elements[i]));
        }
        root = list.get(0);//指定根节点
        //为二叉树指针赋值
        for (int j = 0; j < list.size()/2; j++) {
            //为左子树赋值
            list.get(j).left = list.get(j*2+1).val==0?null:list.get(j*2+1);
            //为右子树赋值
            list.get(j).right = list.get(j*2+2).val==0?null:list.get(j*2+2);
        }
        return root;
    }
    public static int getMaxDepth(TreeNode root){
        if(root == null){
            return 0;
        }
        //DFS(后序遍历)
//        int res = Math.max(getMaxDepth(root.left),getMaxDepth(root.right))+1;
        //BFS(层序遍历)
        int res = 0;
        LinkedList<TreeNode> ll = new LinkedList<>(),tmp;
        ll.add(root);
        while(!ll.isEmpty()){//对树的每一层进行循环
            tmp = new LinkedList<>();
            for (TreeNode node:ll) {//将一层中的所有节点都放入一个队列中
                if(node.left != null){
                    tmp.add(node.left);
                }
                if(node.right != null){
                    tmp.add(node.right);
                }
            }
            ll = tmp;
            res++;
        }
        return res;
    }

    public static List<Integer> rightSideView(TreeNode root){
        List<Integer> list = new ArrayList<>();
        if(root == null){
            return list;
        }
        LinkedList<TreeNode> ll = new LinkedList<>(),tmp;
        ll.add(root);
        list.add(root.val);
        while (!ll.isEmpty()){
            tmp = new LinkedList<>();
            for (TreeNode node:ll) {
                if(node.left != null){
                    tmp.add(node.left);
                }
                if(node.right != null) {
                    tmp.add(node.right);
                }
            }
            ll = tmp;
            if(ll.size() > 0){
                list.add(ll.getLast().val);
            }
        }
        return list;
    }

    public static List<Integer> getLeaf(TreeNode root,List<Integer> list){
        TreeNode left = root.left;
        TreeNode right = root.right;
        if(left == null && right == null){
            list.add(root.val);
        }
        if(left != null){
            getLeaf(left,list);
        }
        if(right != null){
            getLeaf(right,list);
        }
        return list;
    }
}
